package unionfindset;

import java.util.Arrays;

public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }

    /**
     * 查找数据x的根节点
     * @param x
     * @return 下标
     */
    public int findRoot(int x) {
        //特判
        if (x < 0) {
            throw new IndexOutOfBoundsException("下标不合法，是负数");
        }
        while (elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    /**
     * 查询x1和x2是不是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1,int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        return index1==index2;
    }

    /**
     * 合并x1和x2的根节点的两个集合（x2并入x1）
     * @param x1
     * @param x2
     */
    public void union(int x1,int x2) {
        //1.分别找到当前x1和x2的根节点
        int root1 = findRoot(x1);
        int root2 = findRoot(x2);

        if(root1 == root2) return;

        //2.合并（更新孩子的数量+更新另一颗树的根节点）
        //更新孩子的数量
        elem[root1] = elem[root1] + elem[root2];
        //更新另一颗树的根节点
        elem[root2] = root1;
    }

    /**
     * 当前集合的个数（不是元素的个数）
     * @return
     */
    public int getCount() {
        int count = 0;
        for(int x:elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }

    /**
     * 打印整个并查集
     */
    public void print() {
        for(int x:elem) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    public static void main1(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        System.out.println("合并：0和6");
        unionFindSet.union(0,6);
        System.out.println("合并：0和7");
        unionFindSet.union(0,7);
        System.out.println("合并：0和8");
        unionFindSet.union(0,8);

        System.out.println("合并：1和4");
        unionFindSet.union(1,4);
        System.out.println("合并：1和9");
        unionFindSet.union(1,9);

        System.out.println("合并：2和3");
        unionFindSet.union(2,3);
        System.out.println("合并：2和5");
        unionFindSet.union(2,5);

        unionFindSet.print();

        System.out.println("合并：8和1");
        unionFindSet.union(8,1);

        System.out.println("查找是不是在同一个集合");
        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
    }
    //T0：亲戚题
    public static void main2(String[] args) {
        int n = 10;
        int m = 3;//三组集合（三对亲戚）
        int p = 2;

        UnionFindSet unionFindSet = new UnionFindSet(n);

        System.out.println("合并：0和6");
        unionFindSet.union(0,6);
        unionFindSet.union(0,1);
        System.out.println("合并：0和7");
        unionFindSet.union(0,7);
        System.out.println("合并：4和8");
        unionFindSet.union(4,8);

        System.out.println("以下不是亲戚：");
        boolean flg = unionFindSet.isSameUnionFindSet(1,6);
        if(flg) {
            System.out.println("是亲戚！");
        } else {
            System.out.println("不是亲戚！");
        }

        System.out.println("当前的亲戚有 " + unionFindSet.getCount() + " 对");
    }
    //T1:省份的数量
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFindSet unionFindSet = new UnionFindSet(n);
        for(int i=0;i<n;i++) {
            for(int j=0;j<isConnected[i].length;j++) {
                if(isConnected[i][j] == 1) {
                    unionFindSet.union(i,j);
                }
            }
        }
        return unionFindSet.getCount();
    }

    //T2:等式方程的可满足性
    //遇到等号就合并，同时判断两个元素是否在不同集合，在直接返回false
    public boolean equationsPossible(String[] equations) {
        //小写字母:但是存入的时候就需要存入字母对应的下标
        UnionFindSet ufs = new UnionFindSet(26);

        for(String x:equations) {
            if(x.charAt(1) == '=') {
                ufs.union(x.charAt(3)-'a',x.charAt(0)-'a');
            }
        }


        for(String x:equations) {
            if(x.charAt(1) == '!') {
                int root1 = ufs.findRoot(x.charAt(3)-'a');
                int root2 = ufs.findRoot(x.charAt(0)-'a');
                if(root1 == root2) {
                    return false;
                }
            }
        }
        return true;
    }
}
